package com.cty._01_Base._05_ReplaceSpaces;

/**
 * @Auther: cty
 * @Date: 2020/6/26 10:16
 * @Description: 面试题5：替换空格
 * 题目：
 *      请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。
 * @version: 1.0
 */
public class ReplaceSpaces {
    /**
     * 用“%20”替换字符串中的空格
     * 效率：
     *      时间  O(N)
     *      空间  O(N)
     * @param str
     * @return
     */
    public static String replaceSpace(String str){
        if(str==null || str.length()==0)
            return null;

        // 统计空格数量
        int spaceNum = 0;
        for(int i=0; i<str.length(); i++)
            if(str.charAt(i) == 32)
                spaceNum++;

        // 将字符串转化为可扩展字符串并扩展
        StringBuilder newStr = new StringBuilder(str);
        for(int i=0; i<2*spaceNum; i++)
            newStr.append(' ');

        // 从后往前替换空格
        int cur = str.length() - 1;
        int rear = str.length() + 2*spaceNum - 1;
        while(cur>=0 && cur<rear){
            if(str.charAt(cur) != 32) {
                newStr.setCharAt(rear--, str.charAt(cur));
            }else {
                newStr.setCharAt(rear--, '0');
                newStr.setCharAt(rear--, '2');
                newStr.setCharAt(rear--, '%');
            }  // end else
            cur--;
        }  // end while

        return newStr.toString();
    }  // end replaceSpace

}  // end OQ5{}
